/** vue的diff过程 */
// old array a b c d e f g
// new array a b e d c h f g

/**
 * 新老vdom的数组diff比较
 * @description
 * @author luyaxiang
 * @date 2022/01/04
 * @param {*} c1 老的vdom array
 * @param {*} c2 新的vdom array
 * @param {*} { mountElement, patch, unmount, move } { 新增, 复用, 卸载, 移动 }
 */
 exports.diffArray = (c1, c2, { mountElement, patch, unmount, move }) => {
  function isSameVNodeType(n1, n2) {
    return n1.key === n2.key;
  }
  /** 前面下标 */
  let i = 0;
  const l2 = c2.length;
  /** 老vdom后面的下标 */
  let e1 = c1.length - 1;
  /** 新vdom后面的下标 */
  let e2 = l2 - 1;
  /** 1.左侧按序查找新老vdom，如果节点不能复用，则停止 */
  while(i <= e1 && i <= e2) {
    const n1 = c1[i];
    const n2 = c2[i];
    if (isSameVNodeType(n1, n2)) {
      // 节点可以复用，使用patch方法
      patch(n1.key);
    } else {
      break;
    }
    i++;
  }
  /**
   * 2.右侧按序查找新老vdom，如果节点不能复用，则停止。
   * 注：这里改变的是最后下标的位置 */
  while(i<=e1 && i <= e2) {
    const n1 = c1[e1];
    const n2 = c2[e2];
    if (isSameVNodeType(n1, n2)) {
      patch(n1.key)
    } else {
      break;
    }
    e1--;
    e2--;
  }

  /** 前两步结束后，两个数组剩余：
   * old array [c d e]
   * new array [e d c h]
   */
  // 3.老节点没了
  if (i > e1) {
    // 老节点没了，新节点还有。全部都是新增
    if(i <= e2) {
      while(i <= e2) {
        const n2 = c2[i];
        mountElement(n2.key)
        i++;
      }
    }
  } else if (i > e2) {
    // 4.如果老节点还有；新节点没有；剩余老节点逐个删除
    while(i <= e1) {
      const n1 = c1[i];
      unmount(n1.key);
      i++;
    }
  } else {
    // ! 重要加核心
    // old array: c d e
    // new array: e d c h
    // 5.新老vdom都存在
    // 5.1 遍历新vdom数组，把它做成Map key:index
    const keyToIndexMap = new Map();
    /** 老vdom乱序的起始位置下标 */
    const s1 = i;
    /** 新vdom乱序的起始位置下标 */
    const s2 = i;
    for (i = s2; i <= e2; i ++) {
      const nextChild = c2[i];
      keyToIndexMap.set(nextChild.key, i);
    }
    /** 标记还有多少元素要patch */
    let patched = 0;
    /** 标记下新元素还剩下多少元素需要处理。也就是 e d c h 的长度 */
    const toBePatched = e2 - s2 + 1;
    /*
      下标是新节点的相对下标，是新节点的相对下标。对应的value是老节点的下标 + 1；这里+1，是为了标记0下标是没人用
      最长递增子序列也是基于这里
    **/
    const newIndexToOldIndexMap = new Array(toBePatched).fill(0);
    /** 标记下是否有节点移动 */
    let moved = false;
    let maxNewIndexSoFar = 0; // 当前，新节点数组，匹配到的下标最大值
    // 5.2 遍历老vdom(unmount, patch)
    for(i = s1; i <= e1; i ++) {
      const preChild = c1[i];
      if (patched >= toBePatched) { // 剪枝优化：复用个数够了，生效的都是不需要的，unmount就可以
        unmount(preChild.key)
        continue;
      }
      let newIndex = keyToIndexMap.get(preChild.key) // 当前老节点，在新节点数组中的位置下标
      if (newIndex === undefined) { // 没有找到，老节点没人要，需要删除
        unmount(preChild.key)
      } else { // 找到了，复用
        // 更新newIndexToOldIndexMap对应位置的下标（老节点），表示当前新节点newIndex - s2这个位置是可以复用的，复用老节点i + 1下标这个节点
        newIndexToOldIndexMap[newIndex - s2] = i + 1;
        if (newIndex >= maxNewIndexSoFar) {
          maxNewIndexSoFar = newIndex;
        } else { // newIndex < maxNewIndexSoFar
          moved = true;
        }
        patch(preChild.key);
        
        patched++;
      }
    }
    // 5.3 遍历新vdom（mount、move）
    const increasingNewIndexSequece = moved ? getSequence(newIndexToOldIndexMap) : [];
    console.info("increasingNewIndexSequece", increasingNewIndexSequece)
    let lastIndex = increasingNewIndexSequece.length - 1;
    // 从后往前遍历：可以使用appendChild、insertBefore，好操作。没有insertAfter方法
    for (i = toBePatched - 1; i >= 0; i--) {
      const nextIndex = s2 + i;
      const nextChild = c2[nextIndex];
      if (newIndexToOldIndexMap[i] === 0) { // 这个节点没有人用，不可复用
        mountElement(nextChild.key)
      } else if (moved){
        // 是否存在节点移动
        if (lastIndex < 0 || i !== increasingNewIndexSequece[lastIndex]) {
          move(nextChild.key)
        } else {
          lastIndex--;
        }
      }
    }

  /** 获取最长递增子序列 */
  function getSequence(arr) {
    //   初始值是arr，p[i]记录第i个位置的索引
    const recordIndexOfI = arr.slice();
    const result = [0];
    const len = arr.length;

    let resultLastIndex;
    let resultLast;

    for (let i = 0; i < len; i++) {
      const arrI = arr[i];
      if (arrI !== 0) {
        // result最后一个元素
        resultLastIndex = result.length - 1;
        resultLast = result[resultLastIndex];
        if (arr[resultLast] < arrI) {
          recordIndexOfI[i] = resultLast;
          result.push(i);
          continue;
        }
        let left = 0,
          right = resultLastIndex;
        while (left < right) {
          const mid = (left + right) >> 1;
          if (arr[result[mid]] < arrI) {
            left = mid + 1;
          } else {
            right = mid;
          }
        }

        if (arrI < arr[result[left]]) {
          if (left > 0) {
            recordIndexOfI[i] = result[left - 1];
          }
          result[left] = i;
        }
      }
    }

    //  recordIndexOfI记录了正确的索引 result 进而找到最终正确的索引
    resultLastIndex = result.length - 1;
    resultLast = result[resultLastIndex];

    while (resultLastIndex >= 0) {
      result[resultLastIndex] = resultLast;
      resultLast = recordIndexOfI[resultLast];
      resultLastIndex--;
    }

    return result;
  }
  }
}
